"""
例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)
求最大值;

"""


def findGreatestSumOfSubArray(array):
    max = array[0]
    for i, index in zip(array, range(len(array))):
        sum = 0
        for j in array[index:]:
            sum += j
            if sum > max:
                max = sum
    return max


def dynamic_answer(array):
    """
    动态规划法
            F（i）：以array[i]为末尾元素的子数组的和的最大值，子数组的元素的相对位置不变
            F（i）=max（F（i-1）+array[i], array[i]）

            res：所有子数组的和的最大值
            res=max(res，F(i))
    """
    res = len(array) and max(array)     # 寻找最强
    fi = 0                              # 寻找更强
    for i in array:
        fi = max(i, fi + i)
        res = max(res, fi)
    return res
